import java.util.*;

public class Test {
    // 题目1：二叉树展开为链表
    // 给你二叉树的根结点 root ，请你将它展开为一个单链表：
    //
    //展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
    //展开后的单链表应该与二叉树 先序遍历 顺序相同。
    // 迭代的思路：
    // 直接把左子树的最右节点连接到根的右节点，再把根的右子树连接改成左子树，根移动到右节点，依次循环到null也就是右子树的底部
    public void flatten0(TreeNode root) {
        if (root == null) {
            return;
        }
        while (root != null) {
            TreeNode rightMost = root.left;
            if (rightMost != null) {
                while (rightMost.right != null) {
                    rightMost = rightMost.right;
                }
                rightMost.right = root.right;
                root.right = root.left;
                root.left = null;
            }
            root = root.right;
        }
    }

    // 递归方法
    public void flatten(TreeNode root) {
        if(root == null){
            return;
        }

        flatten(root.left);
        TreeNode right = root.right;
        root.right = root.left;
        root.left = null;
        while(root.right != null){
            root = root.right;
        }
        root.right = right;
        flatten(right);
    }

    // 题目2：二叉树的右视图
    // 给定一个二叉树的 根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。
    // 层序遍历，记录下每层最后一个节点的值
    public List<Integer> rightSideView1(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null){
            return list;
        }
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            while(size > 0){
                TreeNode temp = queue.poll();
                if(temp.left != null){
                    queue.offer(temp.left);
                }
                if(temp.right != null){
                    queue.offer(temp.right);
                }
                if(size == 1){
                    list.add(temp.val);
                }
                size--;
            }
        }
        return list;
    }

    // 迭代的方式
    // 按照 「根结点 -> 右子树 -> 左子树」 的顺序访问， 就可以保证每层都是最先访问最右边的节点的。
    int depth = 0;
    List<Integer> list = new LinkedList<>();
    public List<Integer> rightSideView(TreeNode root) {
        dsf(root, 1);
        return list;
    }

    private void dsf(TreeNode root, int height){
        if(root == null) {
            return;
        }

        if(height > depth){
            list.add(root.val);
            depth = height;
        }

        dsf(root.right, height + 1);
        dsf(root.left, height + 1);
    }

    // 非递归前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<>();
        if(root == null){
            return list;
        }
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while(node != null || !stack.isEmpty()){
            while(node != null){
                list.add(node.val);
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            node = node.right;
        }
        return list;
    }

    // 总路径Ⅱ
    List<List<Integer>> lists = new LinkedList<>();
    Deque<Integer> queue = new LinkedList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dsf1(root, targetSum);
        return lists;
    }

    private void dsf1(TreeNode root, int targetSum){
        if(root == null){
            return;
        }
        queue.offer(root.val);
        if(root.left == null && root.right == null && root.val == targetSum){
            lists.add(new LinkedList<>(queue));
        }
        targetSum -= root.val;
        dsf1(root.left, targetSum);
        dsf1(root.right, targetSum);
        queue.pollLast();
    }

    //♥ 题目3：求根节点到叶节点数字之和
    public int sumNumbers(TreeNode root) {
        return dsf2(root, 0);
    }

    private int dsf2(TreeNode root, int preSum){
        if(root == null){
            return 0;
        }

        int sum = preSum * 10 + root.val;
        if(root.left == null && root.right == null ){
            return sum;
        }else{
            return dsf2(root.left, sum) + dsf2(root.right, sum);
        }
    }

    // 另一个我认为使用递归求解十分神奇的题目
    // 二叉树的直径
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        sideNum(root);
        return max;
    }

    private int sideNum(TreeNode root){
        if(root == null){
            return 0;
        }

        int left = sideNum(root.left);
        int right = sideNum(root.right);

        max = Math.max(max, left + right);

        return (left < right ? right : left) + 1;
    }

    // 题目4：岛屿的周长
    public int islandPerimeter(int[][] grid) {
        int sum = 0;
        int m = grid.length;
        int n = grid[0].length;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == 1){
                    if(j + 1 == n || (j + 1 < n) && grid[i][j + 1] == 0){
                        sum++;
                    }
                    if(j - 1 < 0 || (j - 1 >= 0) && grid[i][j - 1] == 0){
                        sum++;
                    }
                    if(i + 1 == m || (i + 1 < m) && grid[i + 1][j] == 0){
                        sum++;
                    }
                    if(i - 1 < 0 || (i - 1 >= 0) && grid[i - 1][j] == 0){
                        sum++;
                    }
                }
            }
        }
        return sum;
    }

    // 题目5：N 叉树的最大深度
    public int maxDepth(Node root) {
        if(root == null){
            return 0;
        }
        int len = root.children.size();
        int max = 0;
        for(int i = 0; i < len; i++){
            max = Math.max(maxDepth(root.children.get(i)), max);
        }
        return max + 1;
    }

    public static void main(String[] args) {
        List<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);

    }

    // 题目6：有序链表转换二叉搜索树
    public TreeNode sortedListToBST(ListNode head) {
        ListNode cur = head;
        int count = 0;
        while(cur != null){
            count++;
            cur = cur.next;
        }
        int[] nums = new int[count];
        for(int i = 0; i < count; i++){
            nums[i] = head.val;
            head = head.next;
        }

        return createTree(nums, 0, count - 1);
    }

    private TreeNode createTree(int[] nums,int start, int end){
        if(start > end){
            return null;
        }

        int mid = (start + end) / 2;

        TreeNode node = new TreeNode(nums[mid]);
        node.left = createTree(nums, start, mid - 1);
        node.right = createTree(nums, mid + 1, end);
        return node;
    }



}